package main.java;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {
    ArrayList<String> arrayList =new ArrayList<>();
    char[] ch;
    public ArrayList<String> Permutation(String str) {
        arrayList.clear();
        ch = str.toCharArray();
        int[] result= new int[ch.length];
        int[] input= new int[ch.length];
        for (int i = 0; i < ch.length; i++) {
            input[i]=i;
        }
        recuision(input,ch.length,result,0);

        return arrayList;
    }

    /**
     * @param input
     * @param number input的工作下标（已完成的个数）
     * @param result
     * @param resultIndex
     */
    public void recuision(int[] input,int number,int[] result,int resultIndex){
        if(number==0){
            if(resultIndex==0)
                return;
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < result.length; i++) {
                stringBuilder.append(ch[result[i]]);
            }

            if(!arrayList.contains(stringBuilder.toString()))
                arrayList.add(stringBuilder.toString());
        }
        for (int i = 0; i < input.length ; i++) {
                if(!find(result,input[i],resultIndex)){
                    result[resultIndex]=input[i];
                    recuision(input,number-1,result,resultIndex+1);
                }
        }
    }
    public boolean find(int[] input,int f,int length){
        for (int i = 0; i < length; i++) {
            if (input[i]==f)
                return true;
        }
        return false;
    }
    @Test
    public void test1(){
        Solution solution =new Solution();
        solution.Permutation("");
        System.out.println(solution.arrayList.toString());
        System.out.println(solution.arrayList.size());
    }
}
